Elliptic Curve Cryptography (ECC)
   HOME

TheInfoList



OR:

Elliptic-curve cryptography (ECC) is an approach to
public-key cryptography Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
based on the
algebraic structure In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set of ...
of
elliptic curve In mathematics, an elliptic curve is a smooth, projective, algebraic curve of genus one, on which there is a specified point . An elliptic curve is defined over a field and describes points in , the Cartesian product of with itself. If ...
s over
finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
s. ECC allows smaller keys compared to non-EC cryptography (based on plain Galois fields) to provide equivalent security.Commercial National Security Algorithm Suite and Quantum Computing FAQ
U.S. National Security Agency, January 2016.
Elliptic curves are applicable for
key agreement In cryptography, a key-agreement protocol is a protocol whereby two or more parties can agree on a key in such a way that both influence the outcome. If properly done, this precludes undesired third parties from forcing a key choice on the agreeing ...
,
digital signature A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature, where the prerequisites are satisfied, gives a recipient very high confidence that the message was created b ...
s, pseudo-random generators and other tasks. Indirectly, they can be used for
encryption In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can decip ...
by combining the key agreement with a
symmetric encryption Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both the encryption of plaintext and the decryption of ciphertext. The keys may be identical, or there may be a simple transformation to go between th ...
scheme. Elliptic curves are also used in several
integer factorization In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are suf ...
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
s based on elliptic curves that have applications in cryptography, such as
Lenstra elliptic-curve factorization The Lenstra elliptic-curve factorization or the elliptic-curve factorization method (ECM) is a fast, sub- exponential running time, algorithm for integer factorization, which employs elliptic curves. For general-purpose factoring, ECM is the th ...
.


Rationale

Public-key cryptography is based on the intractability of certain mathematical
problems A problem is a difficulty which may be resolved by problem solving. Problem(s) or The Problem may also refer to: People * Problem (rapper), (born 1985) American rapper Books * Problems (Aristotle), ''Problems'' (Aristotle), an Aristotelian (or ps ...
. Early public-key systems based their security on the assumption that it is difficult to
factor Factor, a Latin word meaning "who/which acts", may refer to: Commerce * Factor (agent), a person who acts for, notably a mercantile and colonial agent * Factor (Scotland), a person or firm managing a Scottish estate * Factors of production, suc ...
a large integer composed of two or more large prime factors. For later elliptic-curve-based protocols, the base assumption is that finding the
discrete logarithm In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b' ...
of a random elliptic curve element with respect to a publicly known base point is infeasible: this is the "elliptic curve discrete logarithm problem" (ECDLP). The security of elliptic curve cryptography depends on the ability to compute a point multiplication and the inability to compute the multiplicand given the original and product points. The size of the elliptic curve, measured by the total number of discrete integer pairs satisfying the curve equation, determines the difficulty of the problem. The U.S.
National Institute of Standards and Technology The National Institute of Standards and Technology (NIST) is an agency of the United States Department of Commerce whose mission is to promote American innovation and industrial competitiveness. NIST's activities are organized into physical sci ...
(NIST) has endorsed elliptic curve cryptography in its
Suite B NSA Suite B Cryptography was a set of cryptographic algorithms Promulgation, promulgated by the National Security Agency as part of its Cryptographic Modernization Program. It was to serve as an interoperable cryptographic base for both unclassi ...
set of recommended algorithms, specifically
elliptic-curve Diffie–Hellman Elliptic-curve Diffie–Hellman (ECDH) is a key agreement protocol that allows two parties, each having an elliptic-curve public–private key pair, to establish a shared secret over an insecure channel. This shared secret may be directly used as a ...
(ECDH) for key exchange and
Elliptic Curve Digital Signature Algorithm In cryptography, the Elliptic Curve Digital Signature Algorithm (ECDSA) offers a variant of the Digital Signature Algorithm (DSA) which uses elliptic-curve cryptography. Key and signature-size As with elliptic-curve cryptography in general, the b ...
(ECDSA) for digital signature. The U.S.
National Security Agency The National Security Agency (NSA) is a national-level intelligence agency of the United States Department of Defense, under the authority of the Director of National Intelligence (DNI). The NSA is responsible for global monitoring, collecti ...
(NSA) allows their use for protecting information classified up to
top secret Classified information is material that a government body deems to be sensitive information that must be protected. Access is restricted by law or regulation to particular groups of people with the necessary security clearance and need to know, ...
with 384-bit keys. However, in August 2015, the NSA announced that it plans to replace Suite B with a new cipher suite due to concerns about
quantum computing Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...
attacks on ECC. While the RSA patent expired in 2000, there may be patents in force covering certain aspects of ECC technology. However some argue that the
US government The federal government of the United States (U.S. federal government or U.S. government) is the national government of the United States, a federal republic located primarily in North America, composed of 50 states, a city within a feder ...
elliptic curve digital signature standard (ECDSA; NIST FIPS 186-3) and certain practical ECC-based key exchange schemes (including ECDH) can be implemented without infringing them, including
RSA Laboratories RSA Security LLC, formerly RSA Security, Inc. and doing business as RSA, is an American computer and network security company with a focus on encryption and encryption standards. RSA was named after the initials of its co-founders, Ron Rivest, ...
and Daniel J. Bernstein. The primary benefit promised by elliptic curve cryptography is a smaller
key size In cryptography, key size, key length, or key space refer to the number of bits in a key used by a cryptographic algorithm (such as a cipher). Key length defines the upper-bound on an algorithm's security (i.e. a logarithmic measure of the fastest ...
, reducing storage and transmission requirements, i.e. that an elliptic curve group could provide the same
level of security In cryptography, security level is a measure of the strength that a cryptographic primitive — such as a cipher or hash function — achieves. Security level is usually expressed as a number of "bits of security" (also security strength ...
afforded by an RSA-based system with a large modulus and correspondingly larger key: for example, a 256-bit elliptic curve public key should provide comparable security to a 3072-bit RSA public key.


History

The use of elliptic curves in cryptography was suggested independently by
Neal Koblitz Neal I. Koblitz (born December 24, 1948) is a Professor of Mathematics at the University of Washington. He is also an adjunct professor with the Centre for Applied Cryptographic Research at the University of Waterloo. He is the creator of hyp ...
and
Victor S. Miller Victor Saul Miller (born 3 March 1947 in Brooklyn, New York) is an American mathematician as a Principal Computer Scientist in the Computer Science Laboratory of SRI International. He received his B.A. in mathematics from Columbia University in ...
in 1985. Elliptic curve cryptography algorithms entered wide use in 2004 to 2005.


Theory

For current cryptographic purposes, an ''elliptic curve'' is a
plane curve In mathematics, a plane curve is a curve in a plane that may be either a Euclidean plane, an affine plane or a projective plane. The most frequently studied cases are smooth plane curves (including piecewise smooth plane curves), and algebraic pla ...
over a
finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
(rather than the real numbers) which consists of the points satisfying the equation: : y^2 = x^3 + ax + b, \, along with a distinguished
point at infinity In geometry, a point at infinity or ideal point is an idealized limiting point at the "end" of each line. In the case of an affine plane (including the Euclidean plane), there is one ideal point for each pencil of parallel lines of the plane. Adj ...
, denoted ∞. The coordinates here are to be chosen from a fixed
finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
of characteristic not equal to 2 or 3, or the curve equation will be somewhat more complicated. This set together with the group operation of elliptic curves is an
abelian group In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commut ...
, with the point at infinity as an identity element. The structure of the group is inherited from the divisor group of the underlying
algebraic variety Algebraic varieties are the central objects of study in algebraic geometry, a sub-field of mathematics. Classically, an algebraic variety is defined as the set of solutions of a system of polynomial equations over the real or complex numbers. Mo ...
: : \mathrm^0 (E) \to \mathrm^0 (E) \simeq E, \,


Cryptographic schemes

Several
discrete logarithm In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b' ...
-based protocols have been adapted to elliptic curves, replacing the group (\mathbb_)^\times with an elliptic curve: * The
Elliptic-curve Diffie–Hellman Elliptic-curve Diffie–Hellman (ECDH) is a key agreement protocol that allows two parties, each having an elliptic-curve public–private key pair, to establish a shared secret over an insecure channel. This shared secret may be directly used as a ...
(ECDH) key agreement scheme is based on the Diffie–Hellman scheme, * The Elliptic Curve Integrated Encryption Scheme (ECIES), also known as Elliptic Curve Augmented Encryption Scheme or simply the Elliptic Curve Encryption Scheme, * The
Elliptic Curve Digital Signature Algorithm In cryptography, the Elliptic Curve Digital Signature Algorithm (ECDSA) offers a variant of the Digital Signature Algorithm (DSA) which uses elliptic-curve cryptography. Key and signature-size As with elliptic-curve cryptography in general, the b ...
(ECDSA) is based on the
Digital Signature Algorithm The Digital Signature Algorithm (DSA) is a Public-key cryptography, public-key cryptosystem and Federal Information Processing Standards, Federal Information Processing Standard for digital signatures, based on the mathematical concept of modular e ...
, * The deformation scheme using Harrison's p-adic Manhattan metric, * The Edwards-curve Digital Signature Algorithm (EdDSA) is based on
Schnorr signature In cryptography, a Schnorr signature is a digital signature produced by the Schnorr signature algorithm that was described by Claus Schnorr. It is a digital signature scheme known for its simplicity, among the first whose security is based on the ...
and uses
twisted Edwards curve In algebraic geometry, the twisted Edwards curves are plane models of elliptic curves, a generalisation of Edwards curves introduced by Daniel J. Bernstein, Bernstein, Birkner, Joye, Tanja Lange, Lange and Peters in 2008. The curve set is named a ...
s, * The
ECMQV MQV (Menezes–Qu–Vanstone) is an authenticated protocol for key agreement based on the Diffie–Hellman scheme. Like other authenticated Diffie–Hellman schemes, MQV provides protection against an active attacker. The protocol can be modified ...
key agreement scheme is based on the
MQV MQV (Menezes–Qu–Vanstone) is an authenticated protocol for key agreement based on the Diffie–Hellman scheme. Like other authenticated Diffie–Hellman schemes, MQV provides protection against an active attacker. The protocol can be modifi ...
key agreement scheme, * The ECQV implicit certificate scheme. At the RSA Conference 2005, the
National Security Agency The National Security Agency (NSA) is a national-level intelligence agency of the United States Department of Defense, under the authority of the Director of National Intelligence (DNI). The NSA is responsible for global monitoring, collecti ...
(NSA) announced
Suite B NSA Suite B Cryptography was a set of cryptographic algorithms Promulgation, promulgated by the National Security Agency as part of its Cryptographic Modernization Program. It was to serve as an interoperable cryptographic base for both unclassi ...
which exclusively uses ECC for digital signature generation and key exchange. The suite is intended to protect both classified and unclassified national security systems and information. Recently, a large number of cryptographic primitives based on bilinear mappings on various elliptic curve groups, such as the Weil and
Tate pairing In mathematics, Tate pairing is any of several closely related bilinear pairings involving elliptic curves or abelian varieties, usually over local or finite fields, based on the Tate duality pairings introduced by and extended by . applied t ...
s, have been introduced. Schemes based on these primitives provide efficient
identity-based encryption ID-based encryption, or identity-based encryption (IBE), is an important primitive of ID-based cryptography. As such it is a type of public-key encryption in which the public key of a user is some unique information about the identity of the user ( ...
as well as pairing-based signatures,
signcryption In cryptography, signcryption is a public-key primitive that simultaneously performs the functions of both digital signature and encryption. Encryption and digital signature are two fundamental cryptographic tools that can guarantee the confidentia ...
,
key agreement In cryptography, a key-agreement protocol is a protocol whereby two or more parties can agree on a key in such a way that both influence the outcome. If properly done, this precludes undesired third parties from forcing a key choice on the agreeing ...
, and proxy re-encryption.


Implementation

Some common implementation considerations include:


Domain parameters

To use ECC, all parties must agree on all the elements defining the elliptic curve, that is, the ''domain parameters'' of the scheme. The size of the field used is typically either prime (and denoted as p) or is a power of two (2^m); the latter case is called ''the binary case'', and also necessitates the choice of an auxiliary curve denoted by ''f''. Thus the field is defined by ''p'' in the prime case and the pair of ''m'' and ''f'' in the binary case. The elliptic curve is defined by the constants ''a'' and ''b'' used in its defining equation. Finally, the cyclic subgroup is defined by its ''generator'' (a.k.a. ''base point'') ''G''. For cryptographic application the order of ''G'', that is the smallest positive number ''n'' such that n G = \mathcal (the
point at infinity In geometry, a point at infinity or ideal point is an idealized limiting point at the "end" of each line. In the case of an affine plane (including the Euclidean plane), there is one ideal point for each pencil of parallel lines of the plane. Adj ...
of the curve, and the
identity element In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
), is normally prime. Since ''n'' is the size of a subgroup of E(\mathbb_p) it follows from Lagrange's theorem that the number h = \frac, E(\mathbb_p), is an integer. In cryptographic applications this number ''h'', called the ''cofactor'', must be small (h \le 4) and, preferably, h = 1. To summarize: in the prime case, the domain parameters are (p,a,b,G,n,h); in the binary case, they are (m,f,a,b,G,n,h). Unless there is an assurance that domain parameters were generated by a party trusted with respect to their use, the domain parameters ''must'' be validated before use. The generation of domain parameters is not usually done by each participant because this involves computing the number of points on a curve which is time-consuming and troublesome to implement. As a result, several standard bodies published domain parameters of elliptic curves for several common field sizes. Such domain parameters are commonly known as "standard curves" or "named curves"; a named curve can be referenced either by name or by the unique
object identifier In computing, object identifiers or OIDs are an identifier mechanism standardized by the International Telecommunication Union (ITU) and ISO/IEC for naming any object, concept, or "thing" with a globally unambiguous persistent name. Syntax and le ...
defined in the standard documents: *
NIST The National Institute of Standards and Technology (NIST) is an agency of the United States Department of Commerce whose mission is to promote American innovation and industrial competitiveness. NIST's activities are organized into physical sci ...

Recommended Elliptic Curves for Government Use
*
SECG In cryptography, the Standards for Efficient Cryptography Group (SECG) is an international consortium founded by Certicom in 1998. The group exists to develop commercial standards for efficient and interoperable cryptography based on elliptic curve ...

SEC 2: Recommended Elliptic Curve Domain Parameters
* ECC Brainpool ()
ECC Brainpool Standard Curves and Curve Generation
SECG test vectors are also available. NIST has approved many SECG curves, so there is a significant overlap between the specifications published by NIST and SECG. EC domain parameters may be either specified by value or by name. If one (despite the above) wants to construct one's own domain parameters, one should select the underlying field and then use one of the following strategies to find a curve with appropriate (i.e., near prime) number of points using one of the following methods: * Select a random curve and use a general point-counting algorithm, for example,
Schoof's algorithm Schoof's algorithm is an efficient algorithm to count points on elliptic curves over finite fields. The algorithm has applications in elliptic curve cryptography where it is important to know the number of points to judge the difficulty of solving t ...
or the
Schoof–Elkies–Atkin algorithm The Schoof–Elkies–Atkin algorithm (SEA) is an algorithm used for finding the order of or calculating the number of points on an elliptic curve over a finite field. Its primary application is in elliptic curve cryptography. The algorithm is an e ...
, * Select a random curve from a family which allows easy calculation of the number of points (e.g.,
Koblitz curve Neal I. Koblitz (born December 24, 1948) is a Professor of Mathematics at the University of Washington. He is also an adjunct professor with the Centre for Applied Cryptographic Research at the University of Waterloo. He is the creator of hyper ...
s), or * Select the number of points and generate a curve with this number of points using the ''complex multiplication'' technique. Several classes of curves are weak and should be avoided: * Curves over \mathbb_ with non-prime ''m'' are vulnerable to
Weil descent In mathematics, restriction of scalars (also known as "Weil restriction") is a functor which, for any finite extension of fields ''L/k'' and any algebraic variety ''X'' over ''L'', produces another variety Res''L''/''k'X'', defined over ''k''. ...
attacks. * Curves such that ''n'' divides p^B-1 (where ''p'' is the characteristic of the field: ''q'' for a prime field, or 2 for a binary field) for sufficiently small ''B'' are vulnerable to Menezes–Okamoto–Vanstone (MOV) attack which applies usual
discrete logarithm problem In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b'' ...
(DLP) in a small-degree extension field of \mathbb_p to solve ECDLP. The bound ''B'' should be chosen so that
discrete logarithm In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b' ...
s in the field \mathbb_ are at least as difficult to compute as discrete logs on the elliptic curve E(\mathbb_q). * Curves such that , E(\mathbb_q), = q are vulnerable to the attack that maps the points on the curve to the additive group of \mathbb_q.


Key sizes

Because all the fastest known algorithms that allow one to solve the ECDLP (
baby-step giant-step In group theory, a branch of mathematics, the baby-step giant-step is a meet-in-the-middle algorithm for computing the discrete logarithm or order of an element in a finite abelian group by Daniel Shanks. The discrete log problem is of fundamenta ...
, Pollard's rho, etc.), need O(\sqrt) steps, it follows that the size of the underlying field should be roughly twice the security parameter. For example, for 128-bit security one needs a curve over \mathbb_q, where q \approx 2^. This can be contrasted with finite-field cryptography (e.g., DSA) which requires 3072-bit public keys and 256-bit private keys, and integer factorization cryptography (e.g., RSA) which requires a 3072-bit value of ''n'', where the private key should be just as large. However, the public key may be smaller to accommodate efficient encryption, especially when processing power is limited. The hardest ECC scheme (publicly) broken to date had a 112-bit key for the prime field case and a 109-bit key for the binary field case. For the prime field case, this was broken in July 2009 using a cluster of over 200
PlayStation 3 The PlayStation 3 (PS3) is a home video game console developed by Sony Interactive Entertainment, Sony Computer Entertainment. The successor to the PlayStation 2, it is part of the PlayStation brand of consoles. It was first released on Novemb ...
game consoles and could have been finished in 3.5 months using this cluster when running continuously. The binary field case was broken in April 2004 using 2600 computers over 17 months. A current project is aiming at breaking the ECC2K-130 challenge by Certicom, by using a wide range of different hardware: CPUs, GPUs, FPGA.


Projective coordinates

A close examination of the addition rules shows that in order to add two points, one needs not only several additions and multiplications in \mathbb_q but also an inversion operation. The inversion (for given x \in \mathbb_q find y \in \mathbb_q such that x y = 1) is one to two orders of magnitude slower than multiplication. However, points on a curve can be represented in different coordinate systems which do not require an inversion operation to add two points. Several such systems were proposed: in the ''projective'' system each point is represented by three coordinates (X,Y,Z) using the following relation: x = \frac, y = \frac; in the ''Jacobian system'' a point is also represented with three coordinates (X,Y,Z), but a different relation is used: x = \frac, y = \frac; in the ''López–Dahab system'' the relation is x = \frac, y = \frac; in the ''modified Jacobian'' system the same relations are used but four coordinates are stored and used for calculations (X,Y,Z,aZ^4); and in the ''Chudnovsky Jacobian'' system five coordinates are used (X,Y,Z,Z^2,Z^3). Note that there may be different naming conventions, for example,
IEEE P1363 IEEE P1363 is an Institute of Electrical and Electronics Engineers (IEEE) standardization project for public-key cryptography. It includes specifications for: * Traditional public-key cryptography (IEEE Std 1363-2000 and 1363a-2004) * Lattice-ba ...
-2000 standard uses "projective coordinates" to refer to what is commonly called Jacobian coordinates. An additional speed-up is possible if mixed coordinates are used.


Fast reduction (NIST curves)

Reduction modulo ''p'' (which is needed for addition and multiplication) can be executed much faster if the prime ''p'' is a pseudo-
Mersenne prime In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form for some integer . They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17t ...
, that is p \approx 2^d; for example, p = 2^ - 1 or p = 2^ - 2^ - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1. Compared to
Barrett reduction In modular arithmetic, Barrett reduction is a reduction algorithm introduced in 1986 by P.D. Barrett. A naive way of computing :c = a \,\bmod\, n \, would be to use a fast division algorithm. Barrett reduction is an algorithm designed to optimiz ...
, there can be an order of magnitude speed-up. The speed-up here is a practical rather than theoretical one, and derives from the fact that the moduli of numbers against numbers near powers of two can be performed efficiently by computers operating on binary numbers with
bitwise operation In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operati ...
s. The curves over \mathbb_p with pseudo-Mersenne ''p'' are recommended by NIST. Yet another advantage of the NIST curves is that they use ''a'' = −3, which improves addition in Jacobian coordinates. According to Bernstein and Lange, many of the efficiency-related decisions in NIST FIPS 186-2 are suboptimal. Other curves are more secure and run just as fast.


Applications

Elliptic curves are applicable for
encryption In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can decip ...
,
digital signature A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature, where the prerequisites are satisfied, gives a recipient very high confidence that the message was created b ...
s, pseudo-random generators and other tasks. They are also used in several
integer factorization In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are suf ...
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
s that have applications in cryptography, such as
Lenstra elliptic-curve factorization The Lenstra elliptic-curve factorization or the elliptic-curve factorization method (ECM) is a fast, sub- exponential running time, algorithm for integer factorization, which employs elliptic curves. For general-purpose factoring, ECM is the th ...
. In 1999, NIST recommended fifteen elliptic curves. Specifically, FIPS 186-4 has ten recommended finite fields: * Five prime fields \mathbb_p for certain primes ''p'' of sizes 192, 224, 256, 384, and bits. For each of the prime fields, one elliptic curve is recommended. * Five binary fields \mathbb_ for ''m'' equal 163, 233, 283, 409, and 571. For each of the binary fields, one elliptic curve and one Koblitz curve was selected. The NIST recommendation thus contains a total of five prime curves and ten binary curves. The curves were ostensibly chosen for optimal security and implementation efficiency. In 2013, ''
The New York Times ''The New York Times'' (''the Times'', ''NYT'', or the Gray Lady) is a daily newspaper based in New York City with a worldwide readership reported in 2020 to comprise a declining 840,000 paid print subscribers, and a growing 6 million paid ...
'' stated that Dual Elliptic Curve Deterministic Random Bit Generation (or Dual_EC_DRBG) had been included as a NIST national standard due to the influence of
NSA The National Security Agency (NSA) is a national-level intelligence agency of the United States Department of Defense, under the authority of the Director of National Intelligence (DNI). The NSA is responsible for global monitoring, collecti ...
, which had included a deliberate weakness in the algorithm and the recommended elliptic curve.
RSA Security RSA Security LLC, formerly RSA Security, Inc. and doing business as RSA, is an American computer and network security company with a focus on encryption and encryption standards. RSA was named after the initials of its co-founders, Ron Rivest, ...
in September 2013 issued an advisory recommending that its customers discontinue using any software based on Dual_EC_DRBG. In the wake of the exposure of Dual_EC_DRBG as "an NSA undercover operation", cryptography experts have also expressed concern over the security of the NIST recommended elliptic curves, suggesting a return to encryption based on non-elliptic-curve groups. Elliptic curve cryptography is used by the cryptocurrency
Bitcoin Bitcoin ( abbreviation: BTC; sign: ₿) is a decentralized digital currency that can be transferred on the peer-to-peer bitcoin network. Bitcoin transactions are verified by network nodes through cryptography and recorded in a public distr ...
.
Ethereum Ethereum is a decentralized, open-source blockchain with smart contract functionality. Ether (Abbreviation: ETH; sign: Ξ) is the native cryptocurrency of the platform. Among cryptocurrencies, ether is second only to bitcoin in market capita ...
version 2.0 makes extensive use of elliptic curve pairs using
BLS signature A BLS digital signature—also known as Boneh–Lynn–Shacham (BLS)—is a cryptography, cryptographic signature scheme which allows a user to verify that a signer is ''authentic''. The scheme uses a Pairing#Pairings in cryptography, bili ...
s—as specified in the
IETF The Internet Engineering Task Force (IETF) is a standards organization for the Internet and is responsible for the technical standards that make up the Internet protocol suite (TCP/IP). It has no formal membership roster or requirements and a ...
draft BLS specification—for cryptographically assuring that a specific Eth2 validator has actually verified a particular transaction.


Security


Side-channel attacks

Unlike most other DLP systems (where it is possible to use the same procedure for squaring and multiplication), the EC addition is significantly different for doubling (''P'' = ''Q'') and general addition (''P'' ≠ ''Q'') depending on the coordinate system used. Consequently, it is important to counteract
side-channel attack In computer security, a side-channel attack is any attack based on extra information that can be gathered because of the fundamental way a computer protocol or algorithm is implemented, rather than flaws in the design of the protocol or algorit ...
s (e.g., timing or simple/differential power analysis attacks) using, for example, fixed pattern window (a.k.a. comb) methods (note that this does not increase computation time). Alternatively one can use an
Edwards curve In mathematics, the Edwards curves are a family of elliptic curves studied by Harold Edwards in 2007. The concept of elliptic curves over finite fields is widely used in elliptic curve cryptography. Applications of Edwards curves to cryptograp ...
; this is a special family of elliptic curves for which doubling and addition can be done with the same operation. Another concern for ECC-systems is the danger of fault attacks, especially when running on
smart card A smart card, chip card, or integrated circuit card (ICC or IC card) is a physical electronic authentication device, used to control access to a resource. It is typically a plastic credit card-sized card with an embedded integrated circuit (IC) c ...
s.


Backdoors

Cryptographic experts have expressed concerns that the
National Security Agency The National Security Agency (NSA) is a national-level intelligence agency of the United States Department of Defense, under the authority of the Director of National Intelligence (DNI). The NSA is responsible for global monitoring, collecti ...
has inserted a
kleptographic Kleptography is the study of stealing information securely and subliminally. The term was introduced by Adam Young and Moti Yung in the Proceedings of Advances in Cryptology—Crypto '96.A. Young, M. Yung, "The Dark Side of Black-Box Cryptography, ...
backdoor into at least one elliptic curve-based pseudo random generator. Internal memos leaked by former NSA contractor
Edward Snowden Edward Joseph Snowden (born June 21, 1983) is an American and naturalized Russian former computer intelligence consultant who leaked highly classified information from the National Security Agency (NSA) in 2013, when he was an employee and su ...
suggest that the NSA put a backdoor in the
Dual EC DRBG Dual_EC_DRBG (Dual Elliptic Curve Deterministic Random Bit Generator) is an algorithm that was presented as a cryptographically secure pseudorandom number generator (CSPRNG) using methods in elliptic curve cryptography. Despite wide public criti ...
standard. One analysis of the possible backdoor concluded that an adversary in possession of the algorithm's secret key could obtain encryption keys given only 32 bytes of PRNG output. The SafeCurves project has been launched in order to catalog curves that are easy to securely implement and are designed in a fully publicly verifiable way to minimize the chance of a backdoor.


Quantum computing attacks

Shor's algorithm Shor's algorithm is a quantum algorithm, quantum computer algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. On a quantum computer, to factor an integer N , Shor's algorithm ...
can be used to break elliptic curve cryptography by computing discrete logarithms on a hypothetical
quantum computer Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...
. The latest quantum resource estimates for breaking a curve with a 256-bit modulus (128-bit security level) are 2330 qubits and 126 billion
Toffoli gate In logic circuits, the Toffoli gate (also CCNOT gate), invented by Tommaso Toffoli, is a universal reversible logic gate, which means that any classical reversible circuit can be constructed from Toffoli gates. It is also known as the "controlle ...
s. For the binary elliptic curve case, 906 qubits are necessary (to break 128 bits of security). In comparison, using Shor's algorithm to break the RSA algorithm requires 4098 qubits and 5.2 trillion Toffoli gates for a 2048-bit RSA key, suggesting that ECC is an easier target for quantum computers than RSA. All of these figures vastly exceed any quantum computer that has ever been built, and estimates place the creation of such computers at a decade or more away. Supersingular Isogeny Diffie–Hellman Key Exchange claimed to provide a post-quantum secure form of elliptic curve cryptography by using isogenies to implement Diffie–Hellman key exchanges. This key exchange uses much of the same field arithmetic as existing elliptic curve cryptography and requires computational and transmission overhead similar to many currently used public key systems. However, new classical attacks undermined the security of this protocol. In August 2015, the NSA announced that it planned to transition "in the not distant future" to a new cipher suite that is resistant to
quantum In physics, a quantum (plural quanta) is the minimum amount of any physical entity (physical property) involved in an interaction. The fundamental notion that a physical property can be "quantized" is referred to as "the hypothesis of quantizati ...
attacks. "Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, necessitating a re-evaluation of our cryptographic strategy."


Invalid curve attack

When ECC is used in
virtual machine In computing, a virtual machine (VM) is the virtualization/emulation of a computer system. Virtual machines are based on computer architectures and provide functionality of a physical computer. Their implementations may involve specialized hardw ...
s, an attacker may use an invalid curve to get a complete PDH private key.


Patents

At least one ECC scheme (
ECMQV MQV (Menezes–Qu–Vanstone) is an authenticated protocol for key agreement based on the Diffie–Hellman scheme. Like other authenticated Diffie–Hellman schemes, MQV provides protection against an active attacker. The protocol can be modified ...
) and some implementation techniques are covered by patents.


Alternative representations

Alternative representations of elliptic curves include: *
Hessian curves In geometry, the Hessian curve is a plane curve similar to folium of Descartes. It is named after the German mathematician Otto Hesse. This curve was suggested for application in elliptic curve cryptography, because arithmetic in this curve represen ...
*
Edwards curves In mathematics, the Edwards curves are a family of elliptic curves studied by Harold Edwards in 2007. The concept of elliptic curves over finite fields is widely used in elliptic curve cryptography. Applications of Edwards curves to cryptogra ...
* Twisted curves *
Twisted Hessian curves In mathematics, the Twisted Hessian curve represents a generalization of Hessian curves; it was introduced in elliptic curve cryptography to speed up the addition and doubling formulas and to have strongly unified arithmetic. In some operations (s ...
*
Twisted Edwards curve In algebraic geometry, the twisted Edwards curves are plane models of elliptic curves, a generalisation of Edwards curves introduced by Daniel J. Bernstein, Bernstein, Birkner, Joye, Tanja Lange, Lange and Peters in 2008. The curve set is named a ...
* Doubling-oriented Doche–Icart–Kohel curve *
Tripling-oriented Doche–Icart–Kohel curve The tripling-oriented Doche–Icart–Kohel curve is a form of an elliptic curve that has been used lately in cryptography; it is a particular type of Weierstrass curve. At certain conditions some operations, as adding, doubling or tripling poin ...
* Jacobian curve *
Montgomery curve In mathematics the Montgomery curve is a form of elliptic curve introduced by Peter L. Montgomery in 1987, different from the usual Weierstrass form. It is used for certain computations, and in particular in different cryptography applications. De ...
s


See also

*
Cryptocurrency A cryptocurrency, crypto-currency, or crypto is a digital currency designed to work as a medium of exchange through a computer network that is not reliant on any central authority, such as a government or bank, to uphold or maintain it. It i ...
*
Curve25519 In cryptography, Curve25519 is an elliptic curve used in elliptic-curve cryptography (ECC) offering 128 bits of security (256-bit key size) and designed for use with the elliptic curve Diffie–Hellman (ECDH) key agreement scheme. It is one of th ...
* FourQ *
DNSCurve DNSCurve is a proposed secure protocol for the Domain Name System (DNS), designed by Daniel J. Bernstein. Description DNSCurve uses Curve25519 elliptic curve cryptography to establish keys used by Salsa20, paired with the message authentication ...
*
RSA (cryptosystem) RSA (Rivest–Shamir–Adleman) is a public-key cryptography, public-key cryptosystem that is widely used for secure data transmission. It is also one of the oldest. The acronym "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leona ...
*
ECC patents Patent-related uncertainty around elliptic curve cryptography (ECC), or ECC patents, is one of the main factors limiting its wide acceptance. For example, the OpenSSL team accepted an ECC patch only in 2005 (in OpenSSL version 0.9.8), despite the f ...
*
Elliptic-curve Diffie–Hellman Elliptic-curve Diffie–Hellman (ECDH) is a key agreement protocol that allows two parties, each having an elliptic-curve public–private key pair, to establish a shared secret over an insecure channel. This shared secret may be directly used as a ...
(ECDH) *
Elliptic Curve Digital Signature Algorithm In cryptography, the Elliptic Curve Digital Signature Algorithm (ECDSA) offers a variant of the Digital Signature Algorithm (DSA) which uses elliptic-curve cryptography. Key and signature-size As with elliptic-curve cryptography in general, the b ...
(ECDSA) *
EdDSA In public-key cryptography, Edwards-curve Digital Signature Algorithm (EdDSA) is a digital signature scheme using a variant of Schnorr signature based on twisted Edwards curves. It is designed to be faster than existing digital signature scheme ...
*
ECMQV MQV (Menezes–Qu–Vanstone) is an authenticated protocol for key agreement based on the Diffie–Hellman scheme. Like other authenticated Diffie–Hellman schemes, MQV provides protection against an active attacker. The protocol can be modified ...
*
Elliptic curve point multiplication Elliptic curve scalar multiplication is the operation of successively adding a point along an elliptic curve to itself repeatedly. It is used in elliptic curve cryptography (ECC) as a means of producing a one-way function. The literature presents ...
* Homomorphic signatures for network coding *
Hyperelliptic curve cryptography Hyperelliptic curve cryptography is similar to elliptic curve cryptography (ECC) insofar as the Jacobian of a hyperelliptic curve is an abelian group in which to do arithmetic, just as we use the group of points on an elliptic curve in ECC. Defini ...
*
Pairing-based cryptography Pairing-based cryptography is the use of a pairing between elements of two cryptographic groups to a third group with a mapping e :G_1 \times G_2 \to G_T to construct or analyze cryptographic systems. Definition The following definition is commonl ...
*
Public-key cryptography Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
*
Quantum cryptography Quantum cryptography is the science of exploiting quantum mechanical properties to perform cryptographic tasks. The best known example of quantum cryptography is quantum key distribution which offers an information-theoretically secure solution ...
*
Supersingular isogeny key exchange Supersingular isogeny Diffie–Hellman key exchange (SIDH or SIKE) is an insecure proposal for a post-quantum cryptographic algorithm to establish a secret key between two parties over an untrusted communications channel. It is analogous to the D ...


Notes


References

* Standards for Efficient Cryptography Group (SECG)
SEC 1: Elliptic Curve Cryptography
Version 1.0, September 20, 2000.
archived
as if Nov 11, 2014) * D. Hankerson, A. Menezes, and S.A. Vanstone, ''Guide to Elliptic Curve Cryptography'', Springer-Verlag, 2004. * I. Blake, G. Seroussi, and N. Smart, ''Elliptic Curves in Cryptography'', London Mathematical Society 265, Cambridge University Press, 1999. * I. Blake, G. Seroussi, and N. Smart, editors, ''Advances in Elliptic Curve Cryptography'', London Mathematical Society 317, Cambridge University Press, 2005. * L. Washington, ''Elliptic Curves: Number Theory and Cryptography'', Chapman & Hall / CRC, 2003.
The Case for Elliptic Curve Cryptography
National Security Agency (archived January 17, 2009)
Online Elliptic Curve Cryptography Tutorial
Certicom Corp. (archive
here
as of March 3, 2016) * K. Malhotra, S. Gardner, and R. Patz, Implementation of Elliptic-Curve Cryptography on Mobile Healthcare Devices, Networking, Sensing and Control, 2007 IEEE International Conference on, London, 15–17 April 2007 Page(s):239–244 * Saikat Basu
A New Parallel Window-Based Implementation of the Elliptic Curve Point Multiplication in Multi-Core Architectures
International Journal of Network Security, Vol. 13, No. 3, 2011, Page(s):234–241 (archive
here
as of March 4, 2016) * Christof Paar, Jan Pelzl
"Elliptic Curve Cryptosystems"
Chapter 9 of "Understanding Cryptography, A Textbook for Students and Practitioners". (companion web site contains online cryptography course that covers elliptic curve cryptography), Springer, 2009. (archive
here
as of April 20, 2016) * Luca De Feo, David Jao, Jerome Plut
Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies
Springer 2011. (archive
here
as of May 7, 2012) * Gustavo Banegas, Daniel J. Bernstein, Iggy Van Hoof, Tanja Lange
Concrete quantum cryptanalysis of binary elliptic curves
Springer 2020. (archive
here
as of June 1, 2020)
Jacques Vélu, ''Courbes elliptiques (...)'', Société Mathématique de France, 57, 1-152, Paris, 1978.


External links


Elliptic Curves
at
Stanford University Stanford University, officially Leland Stanford Junior University, is a private research university in Stanford, California. The campus occupies , among the largest in the United States, and enrolls over 17,000 students. Stanford is consider ...

Interactive introduction to elliptic curves and elliptic curve cryptography with Sage
b
Maike Massierer
and th
CrypTool
team * {{Algebraic curves navbox Elliptic curve cryptography Public-key cryptography Finite fields